package main

type stack[E any] interface {
	push(E)
	pop() *E
	size() int
	isEmpty() bool
}

type sliceStack[E any] struct {
	val []E
}
const emptyStackErr string = "The sliceStack is empty. Cannot pop an item!"

func (s *sliceStack[E]) push(e E) {
	s.val = append(s.val, e)
}

func (s *sliceStack[E]) pop() *E {
	if s.isEmpty() {
		return nil
	}
	var res E = s.val[len(s.val) - 1]
	s.val = s.val[:len(s.val)-1]
	return &res
}

func (s sliceStack[E]) isEmpty() bool {
	return s.size() == 0
}

func (s sliceStack[E]) size() int {
	return len(s.val)
}

func main() {
	s := sliceStack[int]{}
	s.push(1)
	s.push(2)
	s.push(3)
	for !s.isEmpty() {
		println(*s.pop())
	}

	q:= queueUsingStack[string]{}
	q.enqueue("你")
	q.enqueue("好")
	q.enqueue("吗")
	for !q.isEmpty() {
		println(q.size())
		println(*q.dequeue())
	}
}

type queue[E any] interface {
	enqueue(E)
	dequeue() *E
}

type queueUsingStack[E any] struct {
	stack1 sliceStack[E]
	stack2 sliceStack[E]
}

func (q *queueUsingStack[E]) enqueue(e E) {
	q.stack1.push(e)
}

func (q *queueUsingStack[E]) dequeue() *E {
	if q.stack2.isEmpty() {
		for !q.stack1.isEmpty() {
			q.stack2.push(*q.stack1.pop())
		}
	}
	return q.stack2.pop()
}

func (q *queueUsingStack[E]) isEmpty() bool {
	return q.stack1.isEmpty() && q.stack2.isEmpty()
}

func (q *queueUsingStack[E]) size() int {
	return q.stack1.size() + q.stack2.size()
}